package com.itheima;

import lombok.val;
import org.junit.Test;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class ListProblem {

    public boolean isPalindrome(ListNode head) {


        ListNode tmp = head;
        Deque<Integer> stack = new LinkedList<Integer>(); //存储对应的栈，当栈中没有元素时返回true
        while(tmp != null) {
            if(stack.isEmpty()) {
                stack.push(tmp.val);
                tmp = tmp.next;
            }
            else {
                int top = stack.peek();
                if(top == tmp.val) {
                    stack.pop();
                    tmp = tmp.next;
                }
                else {
                    stack.push(tmp.val);
                    tmp = tmp.next;
                }
            }
        }
        return stack.isEmpty() || stack.size() == 1;
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null, tail = null;
        int carry = 0;
        while(l1 != null || l2 != null) {
            int n1 = l1 == null ? 0 : l1.val;
            int n2 = l2 == null ? 0 : l2.val;
            int sum = l1.val + l2.val + carry;
            if(head == null) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if(l1 != null) {
                l1 = l1.next;
            }
            if(l2 != null) {
                l2 = l2.next;
            }
        }
        if(carry > 0) {
            tail.next = new ListNode(carry);
        }
        return head;
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
//        Map<Integer, ListNode> map = new HashMap<Integer, ListNode>();
        ListNode tmp = head;
        int i = 0;
        while(tmp != null) {
            i++;
        }
        int m = i;
        i = 0;
        tmp = head;
        ListNode prev = null;
        while(tmp != null) {
          if(i == m - n) {
              prev.next = tmp.next;
          }
          i++;
          prev = tmp;
          tmp = tmp.next;
        }
        return head;
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode start = null; //开始
        ListNode end = head; //结尾
        Map<Integer, ListNode> map = new HashMap<Integer, ListNode>(); //存储前k个节点

        int i = 0; //计数
        while(end != null) {
            if(i == k) {
                //从map中取出节点并进行反向连接，并清空map
//                ListNode t1 = end;
                if(start == null) {
//                    start = map.get(k - 1);
                    head = map.get(k - 1);
                    ListNode p1 = new ListNode();
                    ListNode p2 = new ListNode();
                    for(int j = i - 1; j >= 1; j--) {
                        p1 = map.get(j);
                        p2 = map.get(j - 1);
                        p1.next = p2;
                    }
                    p2.next = end;
                    start = p2; //这一段最后一个，下一段第一个的前一个
                    i = 0;
                    map.clear();
                } else {
                    ListNode p1 = new ListNode();
                    ListNode p2 = new ListNode();
                    for(int j = i - 1; j >= 1; j--) {
                        p1 = map.get(j);
                        p2 = map.get(j - 1);
                        p1.next = p2;
                    }
                    p2.next = end;
                    start.next = map.get(k - 1);
                    start = p2;
                    i = 0;
                    map.clear();
                }


            } else {
                if(end != null && end.next != null) {
                    map.put(i, end);
                    end = end.next;
                } else {
                    break;
                }
                i++;
            }

        }
        return start;
    }

    @Test
    public void test1() {
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(3);
        l1.next.next.next = new ListNode(4);
        l1.next.next.next.next = new ListNode(5);
        System.out.println(reverseKGroup(l1, 2));
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
